Bienvenue à la Leçon 3 de Concepts d'Intelligence Artificielle (PolyU COMP5511). Dans cette session, nous passons de la recherche de chemin à agent unique à la Recherche Adversariale, où les agents évoluent dans des environnements multi-agents compétitifs. Nous introduisons également les Problèmes de Satisfaction de Contraintes (CSP), un paradigme où l'objectif est de trouver un état qui satisfait un ensemble spécifique de restrictions plutôt qu'un chemin.
Concepts Fondamentaux
- Recherche Adversariale : Se concentre sur des algorithmes comme Minimax et Élagage Alpha-Bêta pour prendre des décisions rationnelles face à un adversaire intelligent.
- Recherche Arborescente Monte-Carlo (MCTS) : Explore la prise de décision probabiliste, servant de base aux IA de jeux modernes comme AlphaGo.
- Satisfaction de Contraintes : Modélise les problèmes à l'aide de Variables, Domaines et Contraintes, résolus par Retour arrière et Recherche Locale.
Analyse de Complexité
Dans les contextes adversariaux, la complexité de l'espace de recherche est souvent définie par le facteur de branchement du jeu
Avertissement sur le Changement de Paradigme
Contrairement à la recherche standard (ex. A* ou BFS) où l'environnement est statique, Recherche Adversariale suppose que l'environnement (l'adversaire) tente activement de minimiser votre réussite. Dans les CSP, l'ordre des actions importe moins que la validité de l'affectation finale.
Pseudo-code Conceptuel : Types d'Agents
1
# Adversarial Agent (Game Theory)
2
functionDecide_Move(state):
3
returnMaximize_Utility(Predict_Opponent_Minimization(state))
4
5
# CSP Solver (Constraint Logic)
6
functionSolve_CSP(variables, constraints):
7
ifAll_Constraints_Satisfied(assignment):
8
returnassignment
9
else:
10
returnBacktrack_Search(variables)
Course Roadmap
Transitioning from Search (Lesson 2) to Strategic Decision Making (Lesson 3).